﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;
//有没有暴力法
//dp[i][j]怎么转移
public class Solution1143
{
    public int LongestCommonSubsequence(string text1, string text2)
    {
        int m = text1.Length;
        int n = text2.Length;
        int[][] dp = new int[m + 1][];//dp[i][j]是长度为i和j的两个子串，有多少公共子序列
        //多一维是为了表示空字符串，dp[0][0]是两个空字符串
        for (int i = 0; i <= m; i++)
        {
            dp[i] = new int[n + 1];
            dp[i][0] = 0;

        }
        for (int j = 0; j <= n; j++)
        {
            dp[0][j] = 0;

        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (text1[i - 1] == text2[j - 1])//当前字符相同
                {

                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    //dp[i][j] = dp[i - 1][j - 1];//不是这样转移，可能当前的字符和另一个串的前一个字符有相同序列
                    dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1]);
                }


            }
        }
        return dp[m][n];

    }
}
class Program1143
{
    static void Main1143(string[] args)
    {

        string text1 = "abcde", text2 = "ace";
        Solution1143 solution1143 = new Solution1143();
        int res = solution1143.LongestCommonSubsequence(text1, text2);
        Console.WriteLine(res);

    }
}
